package bst

import "fmt"

type TraversalFunc func(*Node)

func Apply(node *Node) { fmt.Printf("%d ", node.value) }

// 树遍历: 前序， 中序， 后序， DFS， BFS

func (n *Node) PreOrder(apply TraversalFunc) {
	if n == nil {
		return
	}
	apply(n)
	n.left.PreOrder(apply)
	n.right.PreOrder(apply)
}

func (n *Node) InOrder(apply TraversalFunc) {
	if n == nil {
		return
	}
	n.left.InOrder(apply)
	apply(n)
	n.right.InOrder(apply)
}

func (n *Node) PostOrder(apply TraversalFunc) {
	if n == nil {
		return
	}
	n.left.PostOrder(apply)
	n.right.PostOrder(apply)
	apply(n)
}

func (n *Node) TraversalWithChan() <-chan *Node {
	out := make(chan *Node)
	go func() {
		n.InOrder(func(node *Node) {
			out <- node
		})
		close(out)
	}()
	return out
}

func (n *Node) DFS() { // function 抽象
	if n == nil {
		return
	}
	var stack []*Node // slice 尾部作为栈顶
	stack = append(stack, n)
	for len(stack) != 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]  // 拿掉最后一个 node
		fmt.Printf("%d ", node.value) // apply 操作

		// 右孩子压栈
		if node.right != nil {
			stack = append(stack, node.right)
		}

		// 左孩子压栈
		if node.left != nil {
			stack = append(stack, node.left)
		}
	}
}

// BFS 广度优先遍历， TODO 这个方法目前有问题
func (n *Node) BFS() {
	if n == nil {
		return
	}

	var queue []*Node
	queue = append(queue, n)
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		// 左孩子入队
		if n.left != nil {
			queue = append(queue, node.left)
		}
		// 右孩子入队
		if n.right != nil {
			queue = append(queue, node.right)
		}
	}
}
